#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@sharp>
#
# Distributed under terms of the MIT license.

"""

"""

# class LinkNode:

# LRUCache(3)
# set(1, 1)
# set(2, 2)
# set(3, 3)
# set(4, 4)
# get(4)
# get(3)
# get(2)
# get(1)
# set(5, 5)
# get(1)
# get(2)
# get(3)
# get(4)
# get(5)
# 您的打印日志
# id n 140282061632456 1
# head 1 1 n 2 2
# tail 1 1 n 2 2
# head 2 2 n 3 3
# 2 140282061632680
# tail 1 1 n 3 3
# head 3 3 n 4 4
# tail 2 2 n 4 4
# head 3 3 n 2 2
# tail 4 4 n 2 2
# head 2 2 n 5 5
# 2 140282061632680
# tail 4 4 n 5 5
# head 5 5 n 3 3
# tail 4 4 n 3 3
# head 3 3 n 4 4
# tail 2 2 n 4 4
# head 4 4 n 5 5
# tail 2 2 n 5 5
# 输出
# [4,3,2,-1,-1,-1,3,4,5]
# 期望答案
# [4,3,2,-1,-1,2,3,-1,5]
# 提示
# 请检查你的代码和算法正确性，WA通常是由错误的答案造成的，请思考一下你的算法是否正确。

class Node:
    def __init__(self, key, value, pre=None, next=None):
        self.key = key
        self.value = value

        # if pre is None:
        #     pre = self
        # if  next is None:
        #     next = self

        self.pre = pre
        self.next = next

    def set_loop(self):
        self.pre = self
        self.next = self


class LRUCache:
    """
    @param: capacity: An integer
    """
    def __init__(self, capacity):
        self.max_len = capacity
        self.cur_len = 0
        self.pseudo_head = Node(-100, -100)

        self.hash = {}      # {value: node}

    def get(self, key):
        n = self.hash.get(key)
        if n is None:
            return -1

        result = n.value
        # print('innert n', n.value)
        self.adjust_to_head(n)
        # print('innert after', n.value)
        return result
        # return n.value

    def set(self, key, value):
        n = self.hash.get(key)

        if n is None:
            n = Node(key, value, None, None)
            n.set_loop()
            self.add_new_head(n)
            self.hash[key] = n
        else:
            assert False
            self.adjust_to_head(n)
            n.value = value

    def adjust_to_head(self, n):
        # assert False
        if self.pseudo_head.next is n:
            # 已经是头了
            return

        era_head = self.pseudo_head.next
        era_tail = era_head.pre
        # 过了上面那个判断, 链表中至少有一个节点
        assert era_head is not None
        assert era_tail is not None

        # n在头部节点之后, 简单调换value和hash映射
        if era_head.next is n:
            # print('=================== hit two =====================', n.key, n.value)
            self.hash[era_head.key], self.hash[n.key] = n, era_head
            era_head.value, n.value = n.value, era_head.value
            era_head.key, n.key     = n.key, era_head.key
            # print("swap", self.hash[2].key)
            # print("swap b", id(self.hash[2]))
            # print("era key", era_head.key)
            # print("n key", n.key)
            # # print("swap", self.hash[2].key)
            # print("swap a", id(self.hash[2]))
            return

        # 删除n
        self.delete_node(n)

        # 调整到头部
        self.add_head(n)
        # era_tail = era_head.pre     # 可能因为删除n, 导致era_tail改变
        # self.pseudo_head.next = n

        # n.next = era_head
        # era_head.pre = n

        # n.pre = era_tail
        # era_tail.next = n

    def add_new_head(self, n):
        # if self.cur_len >= self.max_len:
        if len(self.hash) >= self.max_len:
            # print(self.hash)
            # for key, value in self.hash.items():
            #     print("key, value", key, value)
            # print("hit max -------------------  ---------------------")
            self.delete_tail()
            # 删除tail

        # 添加n到头
        self.add_head(n)
        # self.hash[n.key] = n
        # 两个操作都要考虑边界

    def add_head(self, n):
        era_head = self.pseudo_head.next

        if era_head is None:
            self.pseudo_head.next = n
            assert n.next is n
            assert n.pre is n
            print("id n", id(n), n.key)
            return

        era_tail = era_head.pre
        # print("n.next", n.pre.key, n.pre.value)
        print('head', era_head.key, era_head.value, 'n', n.key, n.value)
        if era_head.key == 2:
            print("2", id(era_head))
            # assert era_head.pre is era_head

        print('tail', era_tail.key, era_tail.value, 'n', n.key, n.value)

        n.next = era_head
        era_head.pre = n

        n.pre = era_tail
        era_tail.next = n

        self.pseudo_head.next = n
        # if era_head.next = era_head:
        #     n.next = era_head
        #     n.pre = era_head
        #     era_head.next = n
        #     era_head.pre = n
        #     return


    def delete_node(self, n):
        # assert False
        n_pre = n.pre
        n_next = n.next
        n_pre.next = n_next
        n_next.pre = n_pre
        del self.hash[n.key]

    def delete_tail(self):
        # assert False
        era_head = self.pseudo_head.next
        era_tail = era_head.pre
        if era_head is era_tail:
            self.pseudo_head.next = None
            del self.hash[era_head.key]
            return
        else:
            # print('hit tail -------------------  ---------------------')
            self.delete_node(era_tail)

def test():
    s = LRUCache(2)
    s.set(2, 222)
    # print('get 2', s.get(2))
    s.set(1, 111)

    print('get 1', s.get(1))
    print('get 2', s.get(2))

    s.set(4, 444)

    print(s.get(1))
    print(s.get(2))
    print(s.get(4))

    s.set(5, 555)
    print('get 2', s.get(2))
    print('get 4', s.get(4))
    print('get 5', s.get(5))

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
